package com.vic.datastructure.practice.p2;

import java.util.Arrays;

/**
 * 设任意n个整数存放于数组A[1..n]中，试编写算法，将所有正数排在所有负数前面（要求：算法时间复杂度为O（n））。
 *
 * @author victor
 */
public class P2Test {

    public static void main(String[] args) {
//        int[] arr = {5, -2, 32, 12, -83, 13, 24, -45};
        int[] arr = {5, 2, 32, 12, 83, -13, 24, -45};

        // 数据长度
        int n = arr.length;

        // 数组的头下标
        int i = 0;

        // 数组的尾下标
        int j = n - 1;

        //
        while (i < j) {
            // 从前面找，范围为i~j，找到第一个负数
            while (i < j && arr[i] > 0) {
                i++;
            }
            // 从后面找，范围为i~j，找到第一个正数
            while (i < j && arr[j] < 0) {
                j--;
            }
            // 交换
            if (i < j) {
                int x = arr[i];
                // i++ 向后移动一个位置，那么在执行while语句时不需要再比较i与0
                arr[i++] = arr[j];
                // j-- 后前移动一个位置
                arr[j--] = x;
            }
        }

        System.out.println(Arrays.toString(arr));

    }

}
